SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Persistent data structure</title>

</head>

Persistent data structure

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Persistent_storage" class="mw-redirect" title="Persistent storage">Persistent storage</a>.</div>

In <a href="Computing" title="Computing">computing</a>, a persistent data structure or not ephemeral data structure is a <a href="Data_structure" title="Data structure">data structure</a> that always preserves the previous version of itself when it is modified. Such data structures are effectively <a href="Immutable_object" title="Immutable object">immutable</a>, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. The term was introduced in Driscoll, Sarnak, Sleator, and Tarjan's 1986 article.<a href="#cite_note-Driscoll-1">[1]</a>

A data structure is partially persistent if all versions can be accessed but only the newest version can be modified. The data structure is fully persistent if every version can be both accessed and modified. If there is also a meld or merge operation that can create a new version from two previous versions, the data structure is called confluently persistent. Structures that are not persistent are called ephemeral.<a href="#cite_note-kaplan2-2">[2]</a>

These types of data structures are particularly common in <a href="Logic_programming" title="Logic programming">logical</a> and <a href="Functional_programming" title="Functional programming">functional programming</a>,<a href="#cite_note-kaplan2-2">[2]</a> as languages in those paradigms discourage (or fully forbid) the use of mutable data.

<div class="mw-heading mw-heading2"><h2 id="Partial_versus_full_persistence">Partial versus full persistence</h2></div>

In the partial persistence model, a programmer may query any previous version of a data structure, but may only update the latest version. This implies a <a href="Total_order" title="Total order">linear ordering</a> among each version of the data structure.<a href="#cite_note-3">[3]</a> In the fully persistent model, both updates and queries are allowed on any version of the data structure. In some cases the <a href="Computer_performance" title="Computer performance">performance characteristics</a> of querying or updating older versions of a data structure may be allowed to degrade, as is true with the <a href="Rope_(data_structure)" title="Rope (data structure)">rope data structure</a>.<a href="#cite_note-4">[4]</a> In addition, a data structure can be referred to as confluently persistent if, in addition to being fully persistent, two versions of the same data structure can be combined to form a new version which is still fully persistent.<a href="#cite_note-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Partially_persistent_data_structure">Partially persistent data structure</h2></div>

A type of data structure where user may query any version of the structure but may only update the latest version.

An ephemeral data structure can be converted to partially persistent data structure using a few techniques.

One of the technique is by using randomized version of Van Emde Boas Tree which is created using dynamic perfect hashing. This data structure is created as follows:

<ul><li>A stratified tree with m elements is implemented using dynamic perfect hashing.</li>

<li>The tree is pruned by dividing the m elements into buckets of size log(log n) such that the elements of bucket 1 is smaller than the elements of bucket 2 and so on.</li>

<li>The maximal element in each bucket is stored in the stratified tree and each bucket is stored in the structure as an unordered linked list.</li></ul>

The size of this data structure is bounded by the number of elements stored in the structure that is O(m). The insertion of a new maximal element is done in constant O(1) expected and amortized time. Finally query to find an element can be done in this structure in O(log(log n)) worst-case time.<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="Techniques_for_preserving_previous_versions">Techniques for preserving previous versions</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Copy-on-write">Copy-on-write</h3></div>

One method for creating a persistent data structure is to use a platform provided ephemeral data structure such as an <a href="Mutable_array" class="mw-redirect" title="Mutable array">array</a> to store the data in the data structure and copy the entirety of that data structure. This is an inefficient technique because the entire backing data structure must be copied for each write, leading to worst case <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\cdot m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\cdot m)}</annotation>

</semantics>

</math><img src="./6524d6c1f46df6977167a8605414bf7b7d0f8ff1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.697ex; height:2.843ex;" alt="{\displaystyle O(n\cdot m)}" loading="lazy"> performance characteristics for m modifications of an array of size n.

<a href="Copy-on-write" title="Copy-on-write">Copy-on-write</a> memory management can reduce the price for an update from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(Bu)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(Bu)}</annotation>

</semantics>

</math><img src="./b506498ba562858757cbe18f9c60e00332acd61b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.676ex; height:2.843ex;" alt="{\displaystyle O(Bu)}" loading="lazy">, where B is the memory block size and u the number of pages updated in an operation.

The fat node method is to record all changes made to node fields in the nodes themselves, without erasing old values of the fields. This requires that nodes be allowed to become arbitrarily “fat”. In other words, each fat node contains the same information and <a href="Pointer_(computer_programming)" title="Pointer (computer programming)">pointer</a> fields as an ephemeral node, along with space for an arbitrary number of extra field values. Each extra field value has an associated field name and a version stamp which indicates the version in which the named field was changed to have the specified value. Besides, each fat node has its own version stamp, indicating the version in which the node was created. The only purpose of nodes having version stamps is to make sure that each node only contains one value per field name per version. In order to navigate through the structure, each original field value in a node has a version stamp of zero.

<div class="mw-heading mw-heading4"><h4 id="Complexity_of_fat_node">Complexity of fat node</h4></div>

With using fat node method, it requires O(1) space for every modification: just store the new data. Each modification takes O(1) additional time to store the modification at the end of the modification history. This is an <a href="Amortized_analysis" title="Amortized analysis">amortized time</a> bound, assuming modification history is stored in a growable <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a>. At <a href="Access_time" title="Access time">access time</a>, the right version at each node must be found as the structure is traversed. If m modifications were to be made, then each access operation would have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log m)}</annotation>

</semantics>

</math><img src="./01cc8bc56e37299e3f7da69f923f11e601030fd6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.982ex; height:2.843ex;" alt="{\displaystyle O(\log m)}" loading="lazy"> slowdown resulting from the cost of finding the nearest modification in the array. Alternatively, one can employ the <a href="Van_Emde_Boas_tree" title="Van Emde Boas tree">van Emde Boas tree</a> at each node (possibly the space-efficient version using hashing) to reduce the time for an access to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log \log m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log \log m)}</annotation>

</semantics>

</math><img src="./541113a51c1eaff2598b6e7d8044360d64391ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.341ex; height:2.843ex;" alt="{\displaystyle O(\log \log m)}" loading="lazy"> at the cost of increasing update time to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log \log m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log \log m)}</annotation>

</semantics>

</math><img src="./541113a51c1eaff2598b6e7d8044360d64391ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.341ex; height:2.843ex;" alt="{\displaystyle O(\log \log m)}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Path_copying">Path copying</h3></div>

This method assumes that the data structure is a linked graph of nodes.

On update, a copy is made of all nodes on the path to any node which is about to be modified. These changes must then be cascaded back through the data structure: all nodes that pointed to the old node must be modified to point to the new node instead. These modifications cause more cascading changes, and so on, until the root node is reached.

<div class="mw-heading mw-heading4"><h4 id="Complexity_of_path_copying">Complexity of path copying</h4></div>

With m modifications, this costs O(log m) additive <a href="Lookup" class="mw-redirect" title="Lookup">lookup</a> time. Modification time and space are bounded by the size of the longest path in the data structure and the cost of the update in the ephemeral data structure. In a Balanced Binary Search Tree without parent pointers the worst case modification time complexity is O(log n + update cost). However, in a linked list the worst case modification time complexity is O(n + update cost).

<div class="mw-heading mw-heading3"><h3 id="A_combination">A combination</h3></div>

Driscoll, Sarnak, <a href="Daniel_Sleator" title="Daniel Sleator">Sleator</a>, <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan</a> came up<a href="#cite_note-Driscoll-1">[1]</a> with a way to combine the techniques of fat nodes and path copying, achieving O(1) access slowdown and O(1) amortized overhead in space and time per modification. Their method assumes a linked data structure with at most d incoming pointers to each node, where d is a known constant.

In each node, one modification box is stored. This box can hold one modification to the node—either a modification to one of the pointers, or to the node's key, or to some other piece of node-specific data—and a timestamp for when that modification was applied. Initially, every node's modification box is empty.

Whenever a node is accessed, the modification box is checked, and its timestamp is compared against the access time. (The access time specifies the version of the data structure being considered.) If the modification box is empty, or the access time is before the modification time, then the modification box is ignored and only the normal part of the node is considered. On the other hand, if the access time is after the modification time, then the value in the modification box is used, overriding that value in the node.

Modifying a node works like this. (It is assumed that each modification touches one pointer or similar field.) If the node's modification box is empty, then it is filled with the modification. Otherwise, the modification box is full. A copy of the node is made, but using only the latest values. The modification is performed directly on the new node, without using the modification box. (One of the new node's fields is overwritten and its modification box stays empty.) Finally, this change is cascaded to the node's parent, just like path copying. (This may involve filling the parent's modification box, or making a copy of the parent recursively. If the node has no parent—it's the root—it is added the new root to a <a href="Sorted_array" title="Sorted array">sorted array</a> of roots.)

With this <a href="Algorithm" title="Algorithm">algorithm</a>, given any time t, at most one modification box exists in the data structure with time t. Thus, a modification at time t splits the tree into three parts: one part contains the data from before time t, one part contains the data from after time t, and one part was unaffected by the modification.

<div class="mw-heading mw-heading4"><h4 id="Complexity_of_the_combination">Complexity of the combination</h4></div>

Time and space for modifications require amortized analysis. A modification takes O(1) amortized space, and O(1) amortized time. To see why, use a <a href="Potential_method" title="Potential method">potential function</a> ϕ, where ϕ(T) is the number of full live nodes in T . The live nodes of T are just the nodes that are reachable from the current root at the current time (that is, after the last modification). The full live nodes are the live nodes whose modification boxes are full.

Each modification involves some number of copies, say k, followed by 1 change to a modification box. Consider each of the k copies. Each costs O(1) space and time, but decreases the potential function by one. (First, the node to be copied must be full and live, so it contributes to the potential function. The potential function will only drop, however, if the old node isn't reachable in the new tree. But it is known that it isn't reachable in the new tree—the next step in the algorithm will be to modify the node's parent to point at the copy. Finally, it is known that the copy's modification box is empty. Thus, replaced a full live node has been replaced with an empty live node, and ϕ goes down by one.) The final step fills a modification box, which costs O(1) time and increases ϕ by one.

Putting it all together, the change in ϕ is Δϕ =1 − k. Thus, the algorithm takes O(k +Δϕ)= O(1) space and O(k +Δϕ +1) = O(1) time

<div class="mw-heading mw-heading2"><h2 id="Generalized_form_of_persistence">Generalized form of persistence</h2></div>

Path copying is one of the simple methods to achieve persistency in a certain data structure such as binary search trees. It is nice to have a general strategy for implementing persistence that works with any given data structure. In order to achieve that, we consider a directed graph G. We assume that each vertex v in G has a constant number c of outgoing edges that are represented by pointers. Each vertex has a label representing the data. We consider that a vertex has a bounded number d of edges leading into it which we define as inedges(v). We allow the following different operations on G.

<ul><li>CREATE-NODE(): Creates a new vertex with no incoming or outgoing edges.</li>

<li>CHANGE-EDGE(v, i, u): Changes the ith edge of v to point to u</li>

<li>CHANGE-LABEL(v, x): Changes the value of the data stored at v to x</li></ul>

Any of the above operations is performed at a specific time and the purpose of the persistent graph representation is to be able to access any version of G at any given time. For this purpose we define a table for each vertex v in G. The table contains c columns and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d+1}</annotation>

</semantics>

</math><img src="./056e0c06c828dbe71a0f9021b2828ff176a3d337.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d+1}" loading="lazy"> rows. Each row contains in addition to the pointers for the outgoing edges, a label which represents the data at the vertex and a time t at which the operation was performed. In addition to that there is an array inedges(v) that keeps track of all the incoming edges to v. When a table is full, a new table with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d+1}</annotation>

</semantics>

</math><img src="./056e0c06c828dbe71a0f9021b2828ff176a3d337.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d+1}" loading="lazy"> rows can be created. The old table becomes inactive and the new table becomes the active table.

<div class="mw-heading mw-heading3"><h3 id="CREATE-NODE">CREATE-NODE</h3></div>

A call to CREATE-NODE creates a new table and set all the references to null

<div class="mw-heading mw-heading3"><h3 id="CHANGE-EDGE">CHANGE-EDGE</h3></div>

If we assume that CHANGE-EDGE(v, i, u) is called, then there are two cases to consider.

<ul><li>There is an empty row in the table of the vertex v: In this case we copy the last row in the table and we change the ith edge of vertex v to point to the new vertex u</li>

<li>Table of the vertex v is full: In this case we need to create a new table. We copy the last row of the old table into the new table. We need to loop in the array inedges(v) in order to let each vertex in the array point to the new table created. In addition to that, we need to change the entry v in the inedges(w) for every vertex w such that edge v,w exists in the graph G.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="CHANGE-LABEL">CHANGE-LABEL</h3></div>

It works exactly the same as CHANGE-EDGE except that instead of changing the ith edge of the vertex, we change the ith label.

<div class="mw-heading mw-heading3"><h3 id="Efficiency_of_the_generalized_persistent_data_structure">Efficiency of the generalized persistent data structure</h3></div>

In order to find the efficiency of the scheme proposed above, we use an argument defined as a credit scheme. The credit represents a currency. For example, the credit can be used to pay for a table. The argument states the following:

<ul><li>The creation of one table requires one credit</li>

<li>Each call to CREATE-NODE comes with two credits</li>

<li>Each call to CHANGE-EDGE comes with one credit</li></ul>

The credit scheme should always satisfy the following invariant: Each row of each active table stores one credit and the table has the same number of credits as the number of rows. Let us confirm that the invariant applies to all the three operations CREATE-NODE, CHANGE-EDGE and CHANGE-LABEL.

<ul><li>CREATE-NODE: It acquires two credits, one is used to create the table and the other is given to the one row that is added to the table. Thus the invariant is maintained.</li>

<li>CHANGE-EDGE: There are two cases to consider. The first case occurs when there is still at least one empty row in the table. In this case one credit is used to the newly inserted row. The second case occurs when the table is full. In this case the old table becomes inactive and the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d+1}</annotation>

</semantics>

</math><img src="./056e0c06c828dbe71a0f9021b2828ff176a3d337.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d+1}" loading="lazy"> credits are transformed to the new table in addition to the one credit acquired from calling the CHANGE-EDGE. So in total we have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d+2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d+2}</annotation>

</semantics>

</math><img src="./5a97b684f2aa0314e9054c56d6fd016b3ae25c3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d+2}" loading="lazy"> credits. One credit will be used for the creation of the new table. Another credit will be used for the new row added to the table and the d credits left are used for updating the tables of the other vertices that need to point to the new table. We conclude that the invariant is maintained.</li>

<li>CHANGE-LABEL: It works exactly the same as CHANGE-EDGE.</li></ul>

As a summary, we conclude that having <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{1}}</annotation>

</semantics>

</math><img src="./ee784b70e772f55ede5e6e0bdc929994bff63413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.449ex; height:2.009ex;" alt="{\displaystyle n_{1}}" loading="lazy"> calls to CREATE_NODE and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{2}}</annotation>

</semantics>

</math><img src="./840e456e3058bc0be28e5cf653b170cdbfcc3be4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.449ex; height:2.009ex;" alt="{\displaystyle n_{2}}" loading="lazy"> calls to CHANGE_EDGE will result in the creation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\cdot n_{1}+n_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\cdot n_{1}+n_{2}}</annotation>

</semantics>

</math><img src="./cff0704d4f3e7b117b6bb7be528593b08559881b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.58ex; height:2.509ex;" alt="{\displaystyle 2\cdot n_{1}+n_{2}}" loading="lazy"> tables. Since each table has size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(d)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(d)}</annotation>

</semantics>

</math><img src="./6e323ee705f0664132bf796619cf0e2b36a1c396.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.798ex; height:2.843ex;" alt="{\displaystyle O(d)}" loading="lazy"> without taking into account the recursive calls, then filling in a table requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(dc)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(dc)}</annotation>

</semantics>

</math><img src="./f6f1f7f31357f95c7bf2186e8b8fdda9156acd13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.805ex; height:2.843ex;" alt="{\displaystyle O(dc)}" loading="lazy">. Therefore, the amount of work required to complete a sequence of operations is bounded by the number of tables created multiplied by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(dc)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(dc)}</annotation>

</semantics>

</math><img src="./f6f1f7f31357f95c7bf2186e8b8fdda9156acd13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.805ex; height:2.843ex;" alt="{\displaystyle O(dc)}" loading="lazy">. Each access operation can be done in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(d))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(d))}</annotation>

</semantics>

</math><img src="./c147a8a53e612e439274d27f5a691c292fd8f46b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.58ex; height:2.843ex;" alt="{\displaystyle O(\log(d))}" loading="lazy"> and there are m edge and label operations, thus it requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\cdot O(\log(d))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\cdot O(\log(d))}</annotation>

</semantics>

</math><img src="./9907b23e4705fbb8e94edf3619b9d1e5f1ac6059.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.299ex; height:2.843ex;" alt="{\displaystyle m\cdot O(\log(d))}" loading="lazy">. We conclude that There exists a data structure that can complete any n sequence of CREATE-NODE, CHANGE-EDGE and CHANGE-LABEL and m access operations in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\cdot dc)+m\cdot O(\log(d))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\cdot dc)+m\cdot O(\log(d))}</annotation>

</semantics>

</math><img src="./6ebdd5c80ff387f89fb4115e6937bec83b55d9da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.019ex; height:2.843ex;" alt="{\displaystyle O(n\cdot dc)+m\cdot O(\log(d))}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Applications_of_persistent_data_structures">Applications of persistent data structures</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Next_element_search_or_point_location">Next element search or point location</h3></div>

One of the useful applications that can be solved efficiently using persistence is the Next Element Search. Assume that there are n non intersecting line segments that don't cross each other that are parallel to the x-axis. We want to build a data structure that can query a point p and return the segment above p (if any). We will start by solving the Next Element Search using the naïve method then we will show how to solve it using the persistent data structure method.

<div class="mw-heading mw-heading4"><h4 id="Naïve_method">Naïve method</h4></div>

We start with a vertical line segment that starts off at infinity and we sweep the line segments from the left to the right. We take a pause every time we encounter an end point of these segments. The vertical lines split the plane into vertical strips. If there are n line segments then we can get <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\cdot n+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\cdot n+1}</annotation>

</semantics>

</math><img src="./ab780b6cb9b4ce35cf9db8cf0dab5bbf17a9775f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.239ex; height:2.343ex;" alt="{\displaystyle 2\cdot n+1}" loading="lazy"> vertical strips since each segment has 2 end points. No segment begins and ends in the strip. Every segment either it doesn't touch the strip or it completely crosses it. We can think of the segments as some objects that are in some sorted order from top to bottom. What we care about is where the point that we are looking at fits in this order. We sort the endpoints of the segments by their x coordinate. For each strip <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}}</annotation>

</semantics>

</math><img src="./cfda82668232cbdc0874ed28ab8b6079420d1ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.89ex; height:2.009ex;" alt="{\displaystyle s_{i}}" loading="lazy">, we store the subset segments that cross <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}}</annotation>

</semantics>

</math><img src="./cfda82668232cbdc0874ed28ab8b6079420d1ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.89ex; height:2.009ex;" alt="{\displaystyle s_{i}}" loading="lazy"> in a dictionary. When the vertical line sweeps the line segments, whenever it passes over the left endpoint of a segment then we add it to the dictionary. When it passes through the right endpoint of the segment, we remove it from the dictionary. At every endpoint, we save a copy of the dictionary and we store all the copies sorted by the x coordinates. Thus we have a data structure that can answer any query. In order to find the segment above a point p, we can look at the x coordinate of p to know which copy or strip it belongs to. Then we can look at the y coordinate to find the segment above it. Thus we need two binary searches, one for the x coordinate to find the strip or the copy, and another for the y coordinate to find the segment above it. Thus the query time takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(n))}</annotation>

</semantics>

</math><img src="./7d3f404959a75e486669fd7618e00046eb00bb24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.758ex; height:2.843ex;" alt="{\displaystyle O(\log(n))}" loading="lazy">. In this data structure, the space is the issue since if we assume that we have the segments structured in a way such that every segment starts before the end of any other segment, then the space required for the structure to be built using the naïve method would be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy">. Let us see how we can build another persistent data structure with the same query time but with a better space.

<div class="mw-heading mw-heading4"><h4 id="Persistent_data_structure_method">Persistent data structure method</h4></div>

We can notice that what really takes time in the data structure used in the naïve method is that whenever we move from a strip to the next, we need to take a snap shot of whatever data structure we are using to keep things in sorted order. We can notice that once we get the segments that intersect <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}}</annotation>

</semantics>

</math><img src="./cfda82668232cbdc0874ed28ab8b6079420d1ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.89ex; height:2.009ex;" alt="{\displaystyle s_{i}}" loading="lazy">, when we move to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i+1}}</annotation>

</semantics>

</math><img src="./37ed5b430ba82bf5043261011efbd054e67ae462.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.991ex; height:2.009ex;" alt="{\displaystyle s_{i+1}}" loading="lazy"> either one thing leaves or one thing enters. If the difference between what is in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}}</annotation>

</semantics>

</math><img src="./cfda82668232cbdc0874ed28ab8b6079420d1ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.89ex; height:2.009ex;" alt="{\displaystyle s_{i}}" loading="lazy"> and what is in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i+1}}</annotation>

</semantics>

</math><img src="./37ed5b430ba82bf5043261011efbd054e67ae462.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.991ex; height:2.009ex;" alt="{\displaystyle s_{i+1}}" loading="lazy"> is only one insertion or deletion then it is not a good idea to copy everything from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}}</annotation>

</semantics>

</math><img src="./cfda82668232cbdc0874ed28ab8b6079420d1ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.89ex; height:2.009ex;" alt="{\displaystyle s_{i}}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i+1}}</annotation>

</semantics>

</math><img src="./37ed5b430ba82bf5043261011efbd054e67ae462.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.991ex; height:2.009ex;" alt="{\displaystyle s_{i+1}}" loading="lazy">. The trick is that since each copy differs from the previous one by only one insertion or deletion, then we need to copy only the parts that change. Let us assume that we have a tree rooted at T. When we insert a key k into the tree, we create a new leaf containing k. Performing rotations to rebalance the tree will only modify the nodes of the path from k to T. Before inserting the key k into the tree, we copy all the nodes on the path from k to T. Now we have 2 versions of the tree, the original one which doesn't contain k and the new tree that contains k and whose root is a copy of the root of T. Since copying the path from k to T doesn't increase the insertion time by more than a constant factor then the insertion in the persistent data structure takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(n))}</annotation>

</semantics>

</math><img src="./7d3f404959a75e486669fd7618e00046eb00bb24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.758ex; height:2.843ex;" alt="{\displaystyle O(\log(n))}" loading="lazy"> time. For the deletion, we need to find which nodes will be affected by the deletion. For each node v affected by the deletion, we copy the path from the root to v. This will provide a new tree whose root is a copy of the root of the original tree. Then we perform the deletion on the new tree. We will end up with 2 versions of the tree. The original one which contains k and the new one which doesn't contain k. Since any deletion only modifies the path from the root to v and any appropriate deletion algorithm runs in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(n))}</annotation>

</semantics>

</math><img src="./7d3f404959a75e486669fd7618e00046eb00bb24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.758ex; height:2.843ex;" alt="{\displaystyle O(\log(n))}" loading="lazy">, thus the deletion in the persistent data structure takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(n))}</annotation>

</semantics>

</math><img src="./7d3f404959a75e486669fd7618e00046eb00bb24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.758ex; height:2.843ex;" alt="{\displaystyle O(\log(n))}" loading="lazy">. Every sequence of insertion and deletion will cause the creation of a sequence of dictionaries or versions or trees <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1},S_{2},\dots S_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1},S_{2},\dots S_{i}}</annotation>

</semantics>

</math><img src="./aaf1a537d15eae201c652f1e5430aea390fe174d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.361ex; height:2.509ex;" alt="{\displaystyle S_{1},S_{2},\dots S_{i}}" loading="lazy"> where each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{i}}</annotation>

</semantics>

</math><img src="./de6e810a93f67802ecb603ee0e3324005c6e583e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.225ex; height:2.509ex;" alt="{\displaystyle S_{i}}" loading="lazy"> is the result of operations <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1},S_{2},\dots S_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1},S_{2},\dots S_{i}}</annotation>

</semantics>

</math><img src="./aaf1a537d15eae201c652f1e5430aea390fe174d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.361ex; height:2.509ex;" alt="{\displaystyle S_{1},S_{2},\dots S_{i}}" loading="lazy">. If each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{i}}</annotation>

</semantics>

</math><img src="./de6e810a93f67802ecb603ee0e3324005c6e583e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.225ex; height:2.509ex;" alt="{\displaystyle S_{i}}" loading="lazy"> contains m elements, then the search in each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{i}}</annotation>

</semantics>

</math><img src="./de6e810a93f67802ecb603ee0e3324005c6e583e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.225ex; height:2.509ex;" alt="{\displaystyle S_{i}}" loading="lazy"> takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(m))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(m))}</annotation>

</semantics>

</math><img src="./1e50bfd633371255c84bdf58fb6fe2585b3c11e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.404ex; height:2.843ex;" alt="{\displaystyle O(\log(m))}" loading="lazy">. Using this persistent data structure we can solve the next element search problem in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(n))}</annotation>

</semantics>

</math><img src="./7d3f404959a75e486669fd7618e00046eb00bb24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.758ex; height:2.843ex;" alt="{\displaystyle O(\log(n))}" loading="lazy"> query time and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\cdot \log(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./9340284081350cf4417f898e60e2d134c46f1f43.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.832ex; height:2.843ex;" alt="{\displaystyle O(n\cdot \log(n))}" loading="lazy"> space instead of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy">. Please find below the source code for an example related to the next search problem.

<div class="mw-heading mw-heading2"><h2 id="Examples_of_persistent_data_structures">Examples of persistent data structures</h2></div>

<a href="Purely_functional_data_structure" title="Purely functional data structure">Purely functional data structure</a> are automatically persistent.

Perhaps the simplest persistent data structure is the <a href="Linked_list" title="Linked list">singly linked list</a> or cons-based list, a simple list of objects formed by each carrying a <a href="Reference" title="Reference">reference</a> to the next in the list. This is persistent because the tail of the list can be taken, meaning the last k items for some k, and new nodes can be added in front of it. The tail will not be duplicated, instead becoming shared between the old list and the new list. So long as the contents of the tail are immutable, this sharing will be invisible to the program.

Many common reference-based data structures, such as <a href="Red%E2%80%93black_tree" title="Red–black tree">red–black trees</a>,<a href="#cite_note-sarnak2-7">[7]</a> <a href="Stack_(data_structure)" class="mw-redirect" title="Stack (data structure)">stacks</a>,<a href="#cite_note-okasaki2-8">[8]</a> and <a href="Treap" title="Treap">treaps</a>,<a href="#cite_note-9">[9]</a> can easily be adapted to create a persistent version. Some others need slightly more effort, for example: <a href="Queue_(data_structure)" class="mw-redirect" title="Queue (data structure)">queues</a>, <a href="Double-ended_queue" title="Double-ended queue">dequeues</a>, and extensions including min-deques (which have an additional O(1) operation min returning the minimal element) and random access deques (which have an additional operation of random access with sub-linear, most often logarithmic, complexity).

Persistent data strctures which are based on immutable ("pure functional") structures should be constrasted with structures that used destructive updates (mutation) and are made persistent using the fat node or path copying techniques, described above.

<div class="mw-heading mw-heading3"><h3 id="Linked_lists">Linked lists</h3></div>

Singly <a href="Linked_list" title="Linked list">linked lists</a> are the bread-and-butter data structure in functional languages.<a href="#cite_note-auto-10">[10]</a> Some <a href="ML_programming_language" class="mw-redirect" title="ML programming language">ML</a>-derived languages, like <a href="Haskell_(programming_language)" class="mw-redirect" title="Haskell (programming language)">Haskell</a>, are purely functional because once a node in the list has been allocated, it cannot be modified, only copied, referenced or destroyed by the <a href="Garbage_collection_(computer_science)" title="Garbage collection (computer science)">garbage collector</a> when nothing refers to it. (Note that ML itself is not purely functional, but supports non-destructive list operations subset, that is also true in the <a href="Lisp_(programming_language)" title="Lisp (programming language)">Lisp</a> (LISt Processing) functional language dialects like <a href="Racket_(programming_language)" title="Racket (programming language)">Scheme</a> and <a href="Racket_(programming_language)" title="Racket (programming language)">Racket</a>.)

Consider the two lists:

<pre>xs = [0, 1, 2]

ys = [3, 4, 5]

</pre>

These would be represented in memory by:

where a circle indicates a node in the list (the arrow out representing the second element of the node which is a pointer to another node).

Now concatenating the two lists:

<pre>zs = xs ++ ys

</pre>

results in the following memory structure:

Notice that the nodes in list <code>xs</code> have been copied, but the nodes in <code>ys</code> are shared. As a result, the original lists (<code>xs</code> and <code>ys</code>) persist and have not been modified.

The reason for the copy is that the last node in <code>xs</code> (the node containing the original value <code>2</code>) cannot be modified to point to the start of <code>ys</code>, because that would change the value of <code>xs</code>.

<div class="mw-heading mw-heading3"><h3 id="Trees">Trees</h3></div>

Consider a <a href="Binary_search_tree" title="Binary search tree">binary search tree</a>,<a href="#cite_note-auto-10">[10]</a> where every node in the tree has the <a href="Recursion" title="Recursion">recursive</a> <a href="Invariant_(computer_science)" class="mw-redirect" title="Invariant (computer science)">invariant</a> that all subnodes contained in the left subtree have a value that is less than or equal to the value stored in the node, and subnodes contained in the right subtree have a value that is greater than the value stored in the node.

For instance, the set of data

<pre>xs = [a, b, c, d, f, g, h]

</pre>

might be represented by the following binary search tree:

A function which inserts data into the binary tree and maintains the invariant is:<div class="mw-highlight mw-highlight-lang-ocaml mw-content-ltr" dir="ltr"><pre> fun insert (x, E) = T (E, x, E)

| insert (x, s as T (a, y, b)) =

if x < y then T (insert (x, a), y, b)

else if x > y then T (a, y, insert (x, b))

else s

</pre></div>After executing

<pre>ys = insert ("e", xs)

</pre>

The following configuration is produced:

Notice two points: first, the original tree (<code>xs</code>) persists. Second, many common nodes are shared between the old tree and the new tree. Such persistence and sharing is difficult to manage without some form of <a href="Garbage_collection_(computer_science)" title="Garbage collection (computer science)">garbage collection</a> (GC) to automatically free up nodes which have no live references, and this is why GC is a feature commonly found in <a href="Functional_programming" title="Functional programming">functional programming languages</a>.

<div class="mw-heading mw-heading3"><h3 id="Persistent_hash_array_mapped_trie">Persistent hash array mapped trie</h3></div>

A persistent hash array mapped trie is a specialized variant of a <a href="Hash_array_mapped_trie" title="Hash array mapped trie">hash array mapped trie</a> that will preserve previous versions of itself on any updates. It is often used to implement a general purpose persistent map data structure.<a href="#cite_note-:1-11">[11]</a>

Hash array mapped tries were originally described in a 2001 paper by <a href="Phil_Bagwell" title="Phil Bagwell">Phil Bagwell</a> entitled "Ideal Hash Trees". This paper presented a mutable <a href="Hash_table" title="Hash table">Hash table</a> where "Insert, search and delete times are small and constant, independent of key set size, operations are O(1). Small worst-case times for insert, search and removal operations can be guaranteed and misses cost less than successful searches".<a href="#cite_note-12">[12]</a> This data structure was then modified by <a href="Rich_Hickey" title="Rich Hickey">Rich Hickey</a> to be fully persistent for use in the <a href="Clojure" title="Clojure">Clojure</a> programming language.<a href="#cite_note-13">[13]</a>

Conceptually, hash array mapped tries work similar to any generic <a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">tree</a> in that they store nodes hierarchically and retrieve them by following a path down to a particular element. The key difference is that Hash Array Mapped Tries first use a <a href="Hash_function" title="Hash function">hash function</a> to transform their lookup key into a (usually 32 or 64 bit) integer. The path down the tree is then determined by using slices of the binary representation of that integer to index into a <a href="Sparse_matrix" title="Sparse matrix">sparse array</a> at each level of the tree. The leaf nodes of the tree behave similar to the buckets used to construct <a href="Hash_table" title="Hash table">hash tables</a> and may or may not contain multiple candidates depending on <a href="Hash_collision" title="Hash collision">hash collisions</a>.<a href="#cite_note-:1-11">[11]</a>

Most implementations of persistent hash array mapped tries use a branching factor of 32 in their implementation. This means that in practice while insertions, deletions, and lookups into a persistent hash array mapped trie have a computational complexity of O(log n), for most applications they are effectively constant time, as it would require an extremely large number of entries to make any operation take more than a dozen steps.<a href="#cite_note-14">[14]</a>

<div class="mw-heading mw-heading2"><h2 id="Usage_in_programming_languages">Usage in programming languages</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Haskell">Haskell</h3></div>

Haskell is a <a href="Pure_functional_language" class="mw-redirect" title="Pure functional language">pure functional language</a> and therefore does not allow for mutation. Therefore, all data structures in the language are persistent, as it is impossible to not preserve the previous state of a data structure with functional semantics.<a href="#cite_note-15">[15]</a> This is because any change to a data structure that would render previous versions of a data structure invalid would violate <a href="Referential_transparency" title="Referential transparency">referential transparency</a>.

In its standard library Haskell has efficient persistent implementations for linked lists,<a href="#cite_note-16">[16]</a> Maps (implemented as size balanced trees),<a href="#cite_note-17">[17]</a> and Sets<a href="#cite_note-18">[18]</a> among others.<a href="#cite_note-19">[19]</a>

<div class="mw-heading mw-heading3"><h3 id="Clojure">Clojure</h3></div>

Like many programming languages in the <a href="Lisp_(programming_language)" title="Lisp (programming language)">Lisp</a> family, Clojure contains an implementation of a linked list, but unlike other dialects its implementation of a linked list has enforced persistence instead of being persistent by convention.<a href="#cite_note-20">[20]</a> Clojure also has efficient implementations of persistent vectors, maps, and sets based on persistent hash array mapped tries. These data structures implement the mandatory read-only parts of the <a href="Java_collections_framework" title="Java collections framework">Java collections framework</a>.<a href="#cite_note-21">[21]</a>

The designers of the Clojure language advocate the use of persistent data structures over mutable data structures because they have <a href="Value_semantics" title="Value semantics">value semantics</a> which gives the benefit of making them freely shareable between threads with cheap aliases, easy to fabricate, and language independent.<a href="#cite_note-22">[22]</a>

These data structures form the basis of Clojure's support for <a href="Parallel_computing" title="Parallel computing">parallel computing</a> since they allow for easy retries of operations to sidestep <a href="Data_race" class="mw-redirect" title="Data race">data races</a> and atomic <a href="Compare-and-swap" title="Compare-and-swap">compare and swap</a> semantics.<a href="#cite_note-23">[23]</a>

The <a href="Elm_(programming_language)" title="Elm (programming language)">Elm programming language</a> is purely functional like Haskell, which makes all of its data structures persistent by necessity. It contains persistent implementations of linked lists as well as persistent arrays, dictionaries, and sets.<a href="#cite_note-24">[24]</a>

Elm uses a custom <a href="Document_Object_Model" title="Document Object Model">virtual DOM</a> implementation that takes advantage of the persistent nature of Elm data. As of 2016 it was reported by the developers of Elm that this virtual DOM allows the Elm language to render HTML faster than the popular <a href="JavaScript" title="JavaScript">JavaScript</a> frameworks <a href="React_(JavaScript_library)" class="mw-redirect" title="React (JavaScript library)">React</a>, <a href="Ember.js" title="Ember.js">Ember</a>, and <a href="Angular_(application_platform)" class="mw-redirect" title="Angular (application platform)">Angular</a>.<a href="#cite_note-25">[25]</a>

The <a href="Java_(programming_language)" title="Java (programming language)">Java programming language</a> is not particularly functional. Despite this, the core JDK package java.util.concurrent includes CopyOnWriteArrayList and CopyOnWriteArraySet which are persistent structures, implemented using copy-on-write techniques. The usual concurrent map implementation in Java, ConcurrentHashMap, is not persistent, however. Fully persistent collections are available in third-party libraries,<a href="#cite_note-26">[26]</a> or other JVM languages.

<div class="mw-heading mw-heading3"><h3 id="JavaScript">JavaScript</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

The popular JavaScript frontend framework <a href="React_(JavaScript_library)" class="mw-redirect" title="React (JavaScript library)">React</a> is frequently used along with a state management system that implements the Flux architecture,<a href="#cite_note-27">[27]</a><a href="#cite_note-28">[28]</a> a popular implementation of which is the JavaScript library <a href="Redux_(JavaScript_library)" title="Redux (JavaScript library)">Redux</a>. The Redux library is inspired by the state management pattern used in the Elm programming language, meaning that it mandates that users treat all data as persistent.<a href="#cite_note-29">[29]</a> As a result, the Redux project recommends that in certain cases users make use of libraries for enforced and efficient persistent data structures. This reportedly allows for greater performance than when comparing or making copies of regular JavaScript objects.<a href="#cite_note-:0-30">[30]</a>

One such library of persistent data structures Immutable.js is based on the data structures made available and popularized by Clojure and Scala.<a href="#cite_note-31">[31]</a> It is mentioned by the documentation of Redux as being one of the possible libraries that can provide enforced immutability.<a href="#cite_note-:0-30">[30]</a> Mori.js brings data structures similar to those in Clojure to JavaScript.<a href="#cite_note-32">[32]</a> Immer.js brings an interesting approach where one "creates the next immutable state by mutating the current one".

<a href="#cite_note-33">[33]</a> Immer.js uses native JavaScript objects and not efficient persistent data structures and it might cause performance issues when data size is big.

<div class="mw-heading mw-heading3"><h3 id="Prolog">Prolog</h3></div>

Prolog terms are naturally immutable and therefore data structures are typically persistent data structures. Their performance depends on sharing and garbage collection offered by the Prolog system.<a href="#cite_note-34">[34]</a> Extensions to non-ground Prolog terms are not always feasible because of search space explosion. Delayed goals might mitigate the problem.

Some Prolog systems nevertheless do provide destructive operations like setarg/3, which might come in different flavors, with/without copying and with/without backtracking of the state change. There are cases where setarg/3 is used to the good of providing a new declarative layer, like a constraint solver.<a href="#cite_note-35">[35]</a>

<div class="mw-heading mw-heading3"><h3 id="Scala">Scala</h3></div>

The Scala programming language promotes the use of persistent data structures for implementing programs using "Object-Functional Style".<a href="#cite_note-36">[36]</a> Scala contains implementations of many persistent data structures including linked lists, <a href="Red%E2%80%93black_tree" title="Red–black tree">red–black trees</a>, as well as persistent hash array mapped tries as introduced in Clojure.<a href="#cite_note-37">[37]</a>

<div class="mw-heading mw-heading2"><h2 id="Garbage_collection">Garbage collection</h2></div>

Because persistent data structures are often implemented in such a way that successive versions of a data structure share underlying memory<a href="#cite_note-38">[38]</a> ergonomic use of such data structures generally requires some form of <a href="Automatic_garbage_collection" class="mw-redirect" title="Automatic garbage collection">automatic garbage collection</a> system such as <a href="Reference_counting" title="Reference counting">reference counting</a> or <a href="Mark_and_sweep" class="mw-redirect" title="Mark and sweep">mark and sweep</a>.<a href="#cite_note-39">[39]</a> In some platforms where persistent data structures are used it is an option to not use garbage collection which, while doing so can lead to <a href="Memory_leak" title="Memory leak">memory leaks</a>, can in some cases have a positive impact on the overall performance of an application.<a href="#cite_note-40">[40]</a>

<ul><li><a href="Copy-on-write" title="Copy-on-write">Copy-on-write</a></li>

<li><a href="Navigational_database" title="Navigational database">Navigational database</a></li>

<li><a href="Persistent_data" title="Persistent data">Persistent data</a></li>

<li><a href="Retroactive_data_structures" class="mw-redirect" title="Retroactive data structures">Retroactive data structures</a></li>

<li><a href="Purely_functional_data_structure" title="Purely functional data structure">Purely functional data structure</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFDriscollSarnakSleatorTarjan1986" class="citation book cs1">Driscoll JR, Sarnak N, Sleator DD, Tarjan RE (1986). "Making data structures persistent". Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86. pp. 109–121. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.4630">10.1.1.133.4630</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F12130.12142">10.1145/12130.12142</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89791-193-1</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:364871">364871</a>.</cite>

</li>

<li id="cite_note-kaplan2-2">^ <a href="#cite_ref-kaplan2_2-0">a</a> <a href="#cite_ref-kaplan2_2-1">b</a> <cite id="CITEREFKaplan,_Haim2001" class="citation journal cs1">Kaplan, Haim (2001). <a rel="nofollow" class="external text" href="http://www.math.tau.ac.il/~haimk/papers/persistent-survey.ps">"Persistent data structures"</a>. Handbook on Data Structures and Applications.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFConchonFilliâtre2008" class="citation cs2">Conchon, Sylvain; Filliâtre, Jean-Christophe (2008), "Semi-persistent Data Structures", Programming Languages and Systems, Lecture Notes in Computer Science, vol. 4960, Springer Berlin Heidelberg, pp. 322–336, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-78739-6_25">10.1007/978-3-540-78739-6_25</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540787389</bdi></cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFTiark2011" class="citation book cs1">Tiark, Bagwell, Philip Rompf (2011). RRB-Trees: Efficient Immutable Vectors. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/820379112">820379112</a>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFBrodalMakrisTsichlas2006" class="citation cs2">Brodal, Gerth Stølting; Makris, Christos; Tsichlas, Kostas (2006), "Purely Functional Worst Case Constant Time Catenable Sorted Lists", Algorithms – ESA 2006, Lecture Notes in Computer Science, vol. 4168, Springer Berlin Heidelberg, pp. 172–183, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.70.1493">10.1.1.70.1493</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11841036_18">10.1007/11841036_18</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540388753</bdi></cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFLenhofSmid1994" class="citation journal cs1">Lenhof, Hans-Peter; Smid, Michiel (1994). <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1051/ita/1994280100251">"Using persistent data structures for adding range restrictions to searching problems"</a>. RAIRO - Theoretical Informatics and Applications. 28 (1): 25–49. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1051%2Fita%2F1994280100251">10.1051/ita/1994280100251</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/11858%2F00-001M-0000-0014-AD4F-B">11858/00-001M-0000-0014-AD4F-B</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0988-3754">0988-3754</a>.</cite>

</li>

<li id="cite_note-sarnak2-7"><a href="#cite_ref-sarnak2_7-0">^</a> <cite id="CITEREFNeil_SarnakRobert_E._Tarjan1986" class="citation journal cs1">Neil Sarnak; <a href="Robert_Tarjan" title="Robert Tarjan">Robert E. Tarjan</a> (1986). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20151010204956/http://www.link.cs.cmu.edu/15859-f07/papers/point-location.pdf">"Planar Point Location Using Persistent Search Trees"</a> (PDF). Communications of the ACM. 29 (7): 669–679. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F6138.6151">10.1145/6138.6151</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8745316">8745316</a>. Archived from <a rel="nofollow" class="external text" href="http://www.link.cs.cmu.edu/15859-f07/papers/point-location.pdf">the original</a> (PDF) on 2015-10-10. Retrieved 2011-04-06.</cite>

</li>

<li id="cite_note-okasaki2-8"><a href="#cite_ref-okasaki2_8-0">^</a> <cite id="CITEREFChris_Okasaki" class="citation journal cs1">Chris Okasaki. <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf">"Purely Functional Data Structures (thesis)"</a> (PDF).</cite> <code class="cs1-code">{{cite journal}}</code>: Cite journal requires <code class="cs1-code">|journal=</code> (help)

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFLiljenzin2013" class="citation journal cs1">Liljenzin, Olle (2013). "Confluently Persistent Sets and Maps". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1301.3388">1301.3388</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2013arXiv1301.3388L">2013arXiv1301.3388L</a>.</cite> <code class="cs1-code">{{cite journal}}</code>: Cite journal requires <code class="cs1-code">|journal=</code> (help)

</li>

<li id="cite_note-auto-10">^ <a href="#cite_ref-auto_10-0">a</a> <a href="#cite_ref-auto_10-1">b</a> This example is taken from Okasaki. See the bibliography.

</li>

<li id="cite_note-:1-11">^ <a href="#cite_ref-:1_11-0">a</a> <a href="#cite_ref-:1_11-1">b</a> <cite id="CITEREFBoostCon2017" class="citation cs2">BoostCon (2017-06-13), <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=WT9kmIE3Uis">C++Now 2017: Phil Nash "The Holy Grail!? A Persistent Hash-Array-Mapped Trie for C++"</a>, <a rel="nofollow" class="external text" href="https://ghostarchive.org/varchive/youtube/20211221/WT9kmIE3Uis">archived</a> from the original on 2021-12-21, retrieved 2018-10-22</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFPhil2001" class="citation journal cs1">Phil, Bagwell (2001). <a rel="nofollow" class="external text" href="https://infoscience.epfl.ch/record/64398">"Ideal Hash Trees"</a>.</cite> <code class="cs1-code">{{cite journal}}</code>: Cite journal requires <code class="cs1-code">|journal=</code> (help)

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hickey">"Are We There Yet?"</a>. InfoQ. Retrieved 2018-10-22.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFSteindorferVinju2015" class="citation journal cs1">Steindorfer, Michael J.; Vinju, Jurgen J. (2015-10-23). <a rel="nofollow" class="external text" href="https://ir.cwi.nl/pub/24029">"Optimizing hash-array mapped tries for fast and lean immutable JVM collections"</a>. ACM SIGPLAN Notices. 50 (10): 783–800. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2814270.2814312">10.1145/2814270.2814312</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0362-1340">0362-1340</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10317844">10317844</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.haskell.org/">"Haskell Language"</a>. www.haskell.org. Retrieved 2018-10-22.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html">"Data.List"</a>. hackage.haskell.org. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Map-Strict.html">"Data.Map.Strict"</a>. hackage.haskell.org. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Set.html">"Data.Set"</a>. hackage.haskell.org. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://wiki.haskell.org/Performance/Arrays">"Performance/Arrays - HaskellWiki"</a>. wiki.haskell.org. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://clojure.org/reference/lisps">"Clojure - Differences with other Lisps"</a>. clojure.org. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://clojure.org/reference/data_structures">"Clojure - Data Structures"</a>. clojure.org. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.infoq.com/presentations/Value-Values">"Keynote: The Value of Values"</a>. InfoQ. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://clojure.org/reference/atoms">"Clojure - Atoms"</a>. clojure.org. Retrieved 2018-11-30.</cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://package.elm-lang.org/packages/elm/core/latest/">"core 1.0.0"</a>. package.elm-lang.org. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://elm-lang.org/blog/blazing-fast-html-round-two">"blog/blazing-fast-html-round-two"</a>. elm-lang.org. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/sigbla/sigbla-pds/">"Persistent (immutable) collections for Java and Kotlin"</a>. github.com. Retrieved 2023-12-13.</cite>

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://facebook.github.io/flux/">"Flux | Application Architecture for Building User Interfaces"</a>. facebook.github.io. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFMora2016" class="citation web cs1">Mora, Osmel (2016-07-18). <a rel="nofollow" class="external text" href="https://medium.com/react-ecosystem/how-to-handle-state-in-react-6f2d3cd73a0c">"How to handle state in React"</a>. React Ecosystem. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-29"><a href="#cite_ref-29">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://redux.js.org/">"Read Me - Redux"</a>. redux.js.org. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-:0-30">^ <a href="#cite_ref-:0_30-0">a</a> <a href="#cite_ref-:0_30-1">b</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://redux.js.org/faq/immutabledata">"Immutable Data - Redux"</a>. redux.js.org. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20150809185757/http://facebook.github.io/immutable-js/">"Immutable.js"</a>. facebook.github.io. Archived from <a rel="nofollow" class="external text" href="https://facebook.github.io/immutable-js/">the original</a> on 2015-08-09. Retrieved 2018-10-23.</cite>

</li>

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/immerjs/immer">"Immer"</a>. <a href="GitHub" title="GitHub">GitHub</a>. 26 October 2021.</cite>

</li>

<li id="cite_note-34"><a href="#cite_ref-34">^</a> <cite id="CITEREFDjamboulianBoizumault1993" class="citation cs2">Djamboulian, Ara M.; Boizumault, Patrice (1993), <a rel="nofollow" class="external text" href="https://press.princeton.edu/books/hardcover/9780691637709/the-implementation-of-prolog">The Implementation of Prolog - Patrice Boizumault</a>, Princeton University Press, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780691637709</bdi></cite>

</li>

<li id="cite_note-35"><a href="#cite_ref-35">^</a> <cite class="citation cs2"><a rel="nofollow" class="external text" href="https://lirias.kuleuven.be/retrieve/440562">The Use of Mercury for the Implementation of a Finite Domain Solver - Henk Vandecasteele, Bart Demoen, Joachim Van Der Auwera</a>, 1999</cite>

</li>

<li id="cite_note-36"><a href="#cite_ref-36">^</a> <cite class="citation news cs1"><a rel="nofollow" class="external text" href="https://blog.codecentric.de/en/2015/08/essence-of-object-functional-programming-practical-potential-of-scala/">"The Essence of Object-Functional Programming and the Practical Potential of Scala - codecentric AG Blog"</a>. codecentric AG Blog. 2015-08-31. Retrieved 2018-10-23.</cite>

</li>

<li id="cite_note-37"><a href="#cite_ref-37">^</a> <cite id="CITEREFClojureTV2013" class="citation cs2">ClojureTV (2013-01-07), <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=pNhBQJN44YQ">Extreme Cleverness: Functional Data Structures in Scala - Daniel Spiewak</a>, retrieved 2018-10-23</cite>

</li>

<li id="cite_note-38"><a href="#cite_ref-38">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://kostyukov.net/posts/designing-a-pfds/">"Vladimir Kostyukov - Posts / Slides"</a>. kostyukov.net. Retrieved 2018-11-30.</cite>

</li>

<li id="cite_note-39"><a href="#cite_ref-39">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://wiki.c2.com/?ImmutableObjectsAndGarbageCollection">"Immutable Objects And Garbage Collection"</a>. wiki.c2.com. Retrieved 2018-11-30.</cite>

</li>

<li id="cite_note-40"><a href="#cite_ref-40">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.infoq.com/news/2017/03/java-epsilon-gc">"The Last Frontier in Java Performance: Remove the Garbage Collector"</a>. InfoQ. Retrieved 2018-11-30.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://wiki.edinburghhacklab.com/PersistentRedBlackTreeSet">Lightweight Java implementation of Persistent Red-Black Trees</a></li>

<li><a rel="nofollow" class="external text" href="https://persistent.codeplex.com/">Efficient persistent structures in C#</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/DesaultierMAKK/PersistentBST">PersistentBST</a> on <a href="GitHub" title="GitHub">GitHub</a> - GitHub repo containing implementations of persistent BSTs using Fat Nodes, Copy-on-Write, and Path Copying Techniques. To use the persistent BST implementations, simply clone the repository and follow the instructions provided in the README file.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-21" href="https://en.wikipedia.org/wiki/?title=Persistent_data_structure&oldid=1296635657">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>